package com.ljy.my_study.lintcode.第k大元素;

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;

/** 
* @author James
* @date 2018年9月19日 
*/
public class TestMain {
//	描述
//	在数组中找到第k大的元素
//
//	你可以交换数组中的元素的位置
//
//	您在真实的面试中是否遇到过这个题？  
//	样例
//	给出数组 [9,3,2,4,8]，第三大的元素是 4
//
//	给出数组 [1,2,3,4,5]，第一大的元素是 5，第二大的元素是 4，第三大的元素是 3，以此类推
//
//	挑战
//	要求时间复杂度为O(n)，空间复杂度为O(1)
	
	public static void main(String[] args) {
		TestMain testMain=new TestMain();
		int[] arr= {9,3,2,4,8};
		int[] arr1= {1,2,3,4,5};
		System.out.println(testMain.kthLargestElement(3, arr));
		System.out.println(testMain.kthLargestElement(1, arr1));
	}
	
	public int kthLargestElement(int n, int[] nums) {
		Queue<Integer> queue=new PriorityQueue<>(new Comparator<Integer>() {
			@Override
			public int compare(Integer o1, Integer o2) {
				if(o1>=o2) 
					return -1;
				else
					return 1;
			}
		});
		for(int num:nums) {
			queue.offer(num);
		}
		Integer num=null;
		for(int i=0;i<n;i++) {
			num=queue.poll();
		}
		return num;
	}
}
